package com.fengdi.book.hard;

import com.fengdi.publicObject.TreeNode;

import java.util.*;

public class TreeAndGraph {
    public static class LadderLength {

        // 双向BFS搜索方法 ，降低发散搜索的复杂度
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            // 遍历完整的wordlist列表如果endWord不在列表中显然不存在答案
            // 初始化dict
            HashSet<String> dict = new HashSet<>(wordList);
            System.out.println( dict);
            if(!dict.contains(endWord)) return 0;

            HashSet<String> s1 = new HashSet<>();
            s1.add(beginWord);
            HashSet<String> s2 = new HashSet<>();
            s2.add(endWord);

            int step = 1;
            //
            while(!s1.isEmpty() && !s2.isEmpty()) {
                step++;
                if(s1.size() > s2.size()) {
                    HashSet<String> temp = s1;
                    s1 = s2;
                    s2 = temp;
                }

                // 如果该单词已经出现在 S1或者S2当中，则说明该单词已经不会成为下一步转换了，直接从字典中删除
                for(String word : s1) {
                    dict.remove(word);
                }

                for(String word : s2) {
                    dict.remove(word);
                }

                HashSet<String> temp = new HashSet<>();

                for(String word : s1) {
                    StringBuilder sb = new StringBuilder(word);
                    for(int i = 0; i < sb.length(); i++) {
                        char ch = sb.charAt(i);
                        // 逐个尝试字母
                        for(int k = 0; k < 26; k++) {
                            sb.replace(i, i + 1, Character.toString((char)('a' + k)));
                            if(s2.contains(sb.toString())) return step; //说明双BFS搜索成功
                            if(!dict.contains(sb.toString())) continue; //  如果该单词不在字典中，则说明该单词不会成为下一步转换，直接从字典中删除
                            temp.add(sb.toString());
                        }
                        sb.replace(i, i + 1, Character.toString(ch));
                    }
                }
                s1 = temp;
            }
            return 0;
        }
    }

    public static class Solve {
        private final int[] dx = new int[]{-1, 1 , 0, 0};
        private final int[] dy = new int[]{0, 0 , -1, 1};

        public void solve(char[][] board) {
            // 如果区域的长宽小于等于2，则在任何情况下都不可能被包围
            if (board.length <= 2 || board[0].length <= 2) return;
            int row = board.length;
            int col = board[0].length;

            // 边缘的O一定不可能成为被包围的区域，搜索边缘并进行扩散标记
            for (int i = 0; i < col; i++) {
                if(board[0][i] == 'O') {
                    this.dfs(board, 0, i);
                }
            }

             for (int i = 0; i < col; i++) {
                if(board[row - 1][i] == 'O') {
                    this.dfs(board, row - 1, i);
                }
            }

             for (int i = 0; i < row; i++) {
                if(board[i][0] == 'O') {
                    this.dfs(board, i, 0);
                }
            }
             for (int i = 0; i < row; i++) {
                if(board[i][col - 1] == 'O') {
                    this.dfs(board, i, col - 1);
                }
            }

             for(int i = 0; i < row; i++) {
                 for(int j = 0; j < col; j++) {
                     if ( board[i][j] == 'O') {
                         board[i][j] = 'X';
                     } else if (board[i][j] == 'T') {
                         board[i][j] = 'O';
                     }
                 }
             }
        }

        private void dfs(char[][] board, int x, int y) {
            board[x][y] = 'T';
            for(int i = 0; i < 4; i++) {
                 int nx = x + dx[i];
                 int ny = y + dy[i];
                 if(nx >= 0
                         && nx < board.length
                         && ny >= 0
                         && ny < board[0].length
                         && board[nx][ny] == 'O') { // 满足条件继续扩散
                     dfs(board, nx, ny);
                 }
            }
        }
    }

    public static class LowestCommonAncestor {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q) return root;

            TreeNode left = this.lowestCommonAncestor(root.left, p, q);
            TreeNode right = this.lowestCommonAncestor(root.right, p, q);

            TreeNode res = null;
            switch (this.getFlag(left, right)) {
                case 0: break;
                case 1: res = root; break;
                case 2: res = left; break;
                case 3: res = right; break;
            }

            return res;
        }

        private int getFlag(TreeNode left, TreeNode right) {
            if (left == null && right == null) {
                return 0;
            }else if(left != null && right != null) {
                return 1;
            }else if (left != null) {
                return 2;
            }else {
                return 3;
            }
        }
    }

    public static class MaxPathSum {
        public int maxPathSum(TreeNode root) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return root.val;

            TreeNode maxV = new TreeNode(Integer.MIN_VALUE);
            return Math.max(this.getMaxPath(root, maxV), maxV.val);
        }

        private int getMaxPath(TreeNode root, TreeNode maxValue) {
            if (root == null) return Integer.MIN_VALUE / 10; // 避免溢出

            int left = this.getMaxPath(root.left, maxValue);
            int right = this.getMaxPath(root.right, maxValue);

            int rootVal = root.val;
            int max = Math.max(rootVal, Math.max(rootVal + left, rootVal + right));

            maxValue.val = Math.max(maxValue.val, left);
            maxValue.val = Math.max(maxValue.val, right);
            maxValue.val = Math.max(maxValue.val, rootVal + left + right);
            return max;
        }
    }

    public static class FindCircleNum {
        private int result = 0;

        public int findCircleNum(int[][] isConnected) {
            int cityNum = isConnected.length;
            if (cityNum == 0 || cityNum == 1) return cityNum;

            boolean[] visited = new boolean[cityNum];
            for (int i = 0; i < cityNum; i++) {
                if (visited[i]) continue;
                this.result++;
                this.bfs(isConnected, i, visited);
            }
            return this.result;
        }

        private void bfs(int[][] isConnected, int index, boolean[] visited) {
            if (visited[index] || index >= isConnected.length) return;

            Queue<Integer> queue = new LinkedList<>();

            // 添加所有相连的点
            for (int i = 0; i < isConnected.length; i++) {
                if(isConnected[index][i] == 1) queue.add(i);
            }

            visited[index] = true;

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                this.bfs(isConnected, cur, visited);
                visited[cur] = true;
            }
        }
    }

    public static class CanFinish {

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // 寻找最长的一条拓扑序列，如果存在环则无法完成，如果存在拓扑序列且长度>numCourses则可以完成
            if (prerequisites == null || prerequisites.length == 0) return true;

            // 创建邻接表
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < numCourses; i++) {
                map.put(i, new ArrayList<>());
            }
            for (int[] prerequisite : prerequisites) {
                map.get(prerequisite[1]).add(prerequisite[0]);
            }

            // 深度优先搜索，简单来说只要不存在环就可以完成
            for(int i = 0; i < numCourses; i++) {
                try {
                    this.dfs(map, i, 0, numCourses);
                }catch (RuntimeException e) {
                    return false;
                }
            }

            return true;
        }

        private void dfs(Map<Integer, List<Integer>> map, int k, int depth, int courseNum) {
            if (depth > courseNum) throw new RuntimeException("存在环");
            if (map.get(k).isEmpty()) return;

            for (int i : map.get(k)) {
                this.dfs(map, i, depth + 1, courseNum);
            }
        }
    }

    public static class FindOrder {

        public int[] findOrder(int numCourses, int[][] prerequisites) {
            if(numCourses == 0) return new int[0];
            if(numCourses == 1) return new int[]{0};

            // 创建临接表
            Map<Integer, List<Integer>> graph = this.buildGraph(numCourses, prerequisites);

            List<Integer> help = new ArrayList<Integer>();
            // 搜索入度为0的节点，当某一个节点在邻接表中没有任何的节点指向它时，说明该节点的入度为0，可以加入结果集
            while (!graph.isEmpty()) {
                int beginNode = this.getBeginNode(graph);
                if(beginNode == -1) {
                    return new int[0]; // 存在环
                }
                graph.remove(beginNode);
                help.add(beginNode);
            }
            return this.toArray(help);
        }

        private int getBeginNode(Map<Integer, List<Integer>> graph) {
            // 如果找不到入度为0的节点则返回-1
            for (Integer key : graph.keySet()) {
                // 遍历领接表
                boolean flag = true;
                for(List<Integer> list : graph.values()) {
                    if (list.contains(key)) {
                        flag = false; // 入度不为0
                        break;
                    }
                }
                if(flag) return key;
            }

            return -1;
        }

        private Map<Integer, List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            for(int i = 0; i < numCourses; i++) {
                map.put(i, new ArrayList<>());
            }
            for (int[] prerequisite : prerequisites) {
                map.get(prerequisite[1]).add(prerequisite[0]);
            }
            return map;
        }

        private int[] toArray(List<Integer> list) {
            int[] result = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                result[i] = list.get(i);
            }
            return result;
        }
    }

    // 性能不好，会超时
    public static class LongestIncreasingPath {
        private final int[] dx = new int[]{1, -1, 0, 0};
        private final int[] dy = new int[]{0, 0, 1, -1};

        private int maxLength = 0;

        public int longestIncreasingPath(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) return 0;
            for(int i = 0; i < matrix.length; i++) {
                for(int j = 0; j < matrix[0].length; j++) {
                    List<Integer> path = new ArrayList<>();
                    this.dfs(matrix, i, j, path);
                }
            }

            return this.maxLength;
        }

        private void dfs(int[][] matrix, int x, int y, List<Integer> path) {
            int row = matrix.length;
            int col = matrix[0].length;
            if(x < 0 || x >= row || y < 0 || y >= col) { // 超出边界
                return;
            }

            if(path.isEmpty() || matrix[x][y] > path.get(path.size() - 1)) {
                path.add(matrix[x][y]);
                this.maxLength = Math.max(this.maxLength, path.size());
                for(int i = 0; i < 4; i++) {
                    this.dfs(matrix, x + dx[i], y + dy[i], path);
                }
                path.removeLast();
            }
        }
    }

    public static class LongestIncreasingPathV2 {
        private final int[] dx = new int[]{1, -1, 0, 0};
        private final int[] dy = new int[]{0, 0, 1, -1};
        private int result = 1;

        public int longestIncreasingPath(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) return 0;

            int row = matrix.length;
            int col = matrix[0].length;
            int[][] dp = new int[row][col];
            for(int i = 0; i < row; i++) {
                for(int j = 0; j < col; j++) {
                    if(dp[i][j] == 0) {
                        this.dfs(matrix, i, j, dp);
                        this.result = Math.max(this.result, dp[i][j]);
                    }
                }
            }

            return this.result;
        }

        public void dfs(int[][] matrix, int x, int y, int[][] dp) {
            dp[x][y] = 1;
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && matrix[nx][ny] > matrix[x][y]) {
                    if(dp[nx][ny] == 0) {
                        this.dfs(matrix, nx, ny, dp);
                    }
                    dp[x][y] = Math.max(dp[x][y], dp[nx][ny] + 1);
                }
            }
        }
    }

    public static class CountSmaller {
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> result = new ArrayList<>();
            List<Integer> sortList = new ArrayList<>();
            for (int i = nums.length - 1; i >= 0; i--) {
                int index = this.bFind(sortList, nums[i]);
                sortList.add(index, nums[i]);
                result.add(index);
            }
            Collections.reverse(result);
            return result;
        }

        private <T extends Comparable<T>> int bFind(List<T> list, T target) {
            if(list.isEmpty()) return 0;
            int left = 0, right = list.size() - 1;
            while(left <= right) {
                int mid = left + (right - left) / 2;
                if(list.get(mid).compareTo(target) < 0) {
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }

            return left;
        }
    }

    public static class Partition {
        public List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList<>();
            if(s.isEmpty()) return result;
            if(s.length() == 1) {
                result.add(new ArrayList<>(){
                    {
                        add(s);
                    }
                });
                return result;
            }

            Stack<String> stack = new Stack<>();
            for(int i = 1; i <= s.length(); i++) {
                String pre = s.substring(0, i); // 截取前缀
                String suffix = s.substring(i); // 截取后缀
                this.dfsPartition(result, stack, pre, suffix);
            }

            return result;
        }

        private void dfsPartition(List<List<String>> result, Stack<String> stack, String pre, String suffix) {
            if(!this.isPalindrome(pre)) { // 如果前缀不是回文串，那么以该串为前缀的串也不可能是回文串
                return;
            }

            if (suffix.isEmpty()) { // 后缀为空说明搜索结束，加入结果集
                stack.add(pre);
                result.add(new ArrayList<>(stack));
                stack.pop();
            }

            for(int i = 1; i <= suffix.length(); i++) {
                stack.push(pre);
                String subPre = suffix.substring(0, i);
                String subSuffix = suffix.substring(i);
                this.dfsPartition(result, stack, subPre, subSuffix);
                stack.pop();
            }
        }

        private boolean isPalindrome(String s) {
           if(s.isEmpty()) return false;
           s = s.toLowerCase();
           int l = 0;
           int r = s.length() - 1;
           while(l < r) {
               if(s.charAt(l) != s.charAt(r)) {
                   return false;
               }
               l++;
               r--;
           }
           return true;
        }
    }

    // 超时
    public static class FindWords {
        private final List<String> result = new ArrayList<>();
        private final int[] dx = new int[]{1, -1, 0, 0};
        private final int[] dy = new int[]{0, 0, 1, -1};

        public List<String> findWords(char[][] board, String[] words) {
            if(words.length == 0) return this.result;
            final int row = board.length;
            final int col = board[0].length;

            final List<String> wordList = new ArrayList<>(Arrays.asList(words));

            // 选择起点
            for(int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    boolean[][] visited = new boolean[row][col];
                    StringBuilder sb = new StringBuilder();
                    this.dfs(i, j, sb, board, wordList, visited);
                }
            }

            return this.result;
        }

        private void dfs(int x, int y, StringBuilder sb, char[][] board, List<String> words, boolean[][] visited) {
            if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y]) return;

            visited[x][y] = true;
            sb.append(board[x][y]);
            if(this.hadWord(sb.toString(), words)) {
                words.remove(sb.toString());
                this.result.add(sb.toString());
            }

            if(words.isEmpty()) return;

            for(int i = 0; i < 4; i++) {
                int nx = x + this.dx[i];
                int ny = y + this.dy[i];
                this.dfs(nx, ny, sb, board, words, visited);
            }
            visited[x][y] = false;
            sb.deleteCharAt(sb.length() - 1);
        }

        private boolean hadWord(String s, List<String> list) {
            if(s.isEmpty()) return false;

            for(String word : list) {
                if (s.equals(word)) {
                    return true;
                }
            }

            return false;
        }

    }

    // 最后两个过不了超时
    public static class FindWordsV2 {
        private final List<String> result = new ArrayList<>();

        public List<String> findWords(char[][] board, String[] words) {
            for(String word : words) {
                if(this.exit(board, word)) {
                    this.result.add(word);
                }
            }

            return result;
        }

        private boolean exit(char[][] boards, String s) {
            boolean[][] visited = new boolean[boards.length][boards[0].length];
            char[] ws = s.toCharArray();

            for(int i = 0; i < boards.length; i++) {
                for(int j = 0; j < boards[0].length; j++) {
                    if(boards[i][j] == ws[0]) {
                        if(this.exitTraceBack(i, j, boards, ws, 0, visited)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        private boolean exitTraceBack(int x, int y, char[][] boards, char[] ws, int index, boolean[][] visited) {
            if(index == ws.length) return true;

            if(x < 0 || x >= boards.length || y < 0 || y >= boards[0].length || visited[x][y]) return false;

            if(boards[x][y] != ws[index]) return false;

            visited[x][y] = true;
            boolean a = this.exitTraceBack(x + 1, y, boards, ws, index + 1, visited);
            boolean b = this.exitTraceBack(x - 1, y, boards, ws, index + 1, visited);
            boolean c = this.exitTraceBack(x, y + 1, boards, ws, index + 1, visited);
            boolean d = this.exitTraceBack(x, y - 1, boards, ws, index + 1, visited);
            visited[x][y] = false;
            return a || b || c || d;
        }
    }


    /**
     * @Description 删除无效的括号
     * @Date 09:31
     */
    public static class RemoveInvalidParentheses {
        private final List<String> res = new ArrayList<>();

        public List<String> removeInvalidParentheses(String s) {
            int rremove = 0, lremove = 0;

            // 统计需要删除的左右括号数量
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '(') {
                    lremove++;
                } else if (s.charAt(i) == ')') {
                    if(lremove == 0) {
                        rremove++;
                    }else {
                        lremove--;
                    }
                }
            }

            this.helper(s, 0, lremove, rremove);

            return this.res;
        }

        private void helper(String str, int start, int lremove, int rremove) {
            if(lremove == 0 && rremove == 0) {
                if(this.isValid(str)) {
                    this.res.add(str);
                }
                return;
            }

            for(int i = start; i < str.length(); i++) {
                if(start != i && str.charAt(i) == str.charAt(i - 1)) { // 跳过重复的括号
                    continue;
                }

                if(lremove + rremove > str.length() - i) {// 需要删除的括号超过了剩余字符的长度，不可能合法
                    return;
                }

                String subStr = str.substring(0, i) + str.substring(i + 1);

                if(lremove > 0 && str.charAt(i) == '(') {
                    this.helper(subStr, i, lremove - 1, rremove);
                }

                if (rremove > 0 && str.charAt(i) == ')') {
                    this.helper(subStr, i, lremove, rremove - 1);
                }
            }
        }


        // 检查当前括号字符串是否合法
        private boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            StringBuilder sb = new StringBuilder(s);
            for(int i = 0; i < sb.length(); i++) {
                char ch = sb.charAt(i);
                if(ch == '(') {
                    stack.push('(');
                }else if(ch == ')') {
                    if (stack.isEmpty()) return false;
                    stack.pop();
                }
            }

            return stack.isEmpty();
        }
    }

    /**
     * @Description 通配符匹配
     * @Date 11:04
     */
    public static class IsMatch {
        public boolean isMatch(String s, String p) {
            int sLen = s.length();
            int pLen = p.length();

            boolean[][] dp = new boolean[sLen + 1][pLen + 1]; // dp[i][j]表示p的前j个字符能否匹配s的前i个字符
            dp[0][0] = true;

            for(int i = 1; i <= pLen; i++) {
                if (p.charAt(i - 1) == '*') {
                    dp[0][i] = true;
                }else {
                    break;
                }
            }

            for(int i = 1; i <= sLen; i++) {
                for(int j = 1; j <= pLen; j++) {
                    if(p.charAt(j - 1) == '*') {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    }else if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }

            return dp[sLen][pLen];
        }
    }

    public static class IsMatchEn {
        public boolean isMatch(String s, String p) {
            int sLen = s.length();
            int pLen = p.length();

            boolean[][] dp = new boolean[sLen + 1][pLen + 1];
            dp[0][0] = true;

            for(int i = 0; i <= sLen; i++) {
                for (int j = 1; j <= pLen; j++) {
                    if(p.charAt(j - 1) == '*') {
                        dp[i][j] = dp[i][j - 2];
                        if(this.match(s, p, i, j - 1)) {
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                        }
                    }else {
                        if(this.match(s, p, i, j)) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                }
            }

            return dp[sLen][pLen];
        }

        private boolean match(String s, String p, int i, int j) {
            if(i == 0) return false;
            if (p.charAt(j - 1) == '.') {
                return true;
            }
            return s.charAt(i -1) == p.charAt(j - 1);
        }
    }
}
